package main

import (
	"fmt"
	"math/rand"
)

//!+
type tree struct {
	value       int
	left, right *tree
}

/*
func dfs(t *tree, ans string) string {
	// 递归生成前序序列
	// 方法一：传统方法
	if t == nil {
		return ans
	}
	if t.left != nil {
		ans = dfs(t.left, ans)
	}
	ans = fmt.Sprintf("%s %d", ans, t.value)
	if t.right != nil {
		ans = dfs(t.right, ans)
	}
	return ans
}

func (t *tree) String() string {
	// 输出前序遍历值序列
	return dfs(t, "")
}
*/

func (t *tree) String() string {
	// 输出前序遍历值序列
	// 方法二：使用匿名函数
	var ans = "" // 初始化前序遍历序列
	var dfs func(t *tree)
	dfs = func(t *tree) {
		if t == nil {
			return
		}
		if t.left != nil {
			dfs(t.left) // 匿名函数中使用递归
		}
		ans = fmt.Sprintf("%s %d", ans, t.value)
		if t.right != nil {
			dfs(t.right)
		}
	}
	dfs(t)
	return ans
}

// Sort sorts values in place.
func Sort(values []int) {
	var root *tree
	for _, v := range values {
		root = add(root, v)
	}
	appendValues(values[:0], root)
}

// appendValues appends the elements of t to values in order
// and returns the resulting slice.
func appendValues(values []int, t *tree) []int {
	if t != nil {
		values = appendValues(values, t.left)
		values = append(values, t.value)
		values = appendValues(values, t.right)
	}
	return values
}

func add(t *tree, value int) *tree {
	if t == nil {
		// Equivalent to return &tree{value: value}.
		t = new(tree)
		t.value = value
		return t
	}
	if value < t.value {
		t.left = add(t.left, value)
	} else {
		t.right = add(t.right, value)
	}
	return t
}

func main() {
	data := make([]int, 10)
	for i := range data { // 生成随机数
		data[i] = rand.Int() % 50
	}
	fmt.Println(data)

	var root *tree
	for _, v := range data { // 根据随机数建立二叉排序树
		root = add(root, v)
	}

	fmt.Println(root) // 输出树的前序序列，是一个从小到大排序的序列
}

// 方法二参考：https://github.com/rockyr8/gopl-topics/blob/master/7%E6%8E%A5%E5%8F%A3/ex3.go
